Following the Algorithm Design & Analysis stage (Step 2), we must choose a strategic approach. This fundamental choice—how we structure the computation on input size $n$—is what determines the theoretical complexity $O(f(n))$.

  • Two foundational strategies govern nearly all efficient algorithms: Incremental Approach and Divide-and-Conquer.
  • Incremental Approach: Builds the solution step-by-step, processing one element at a time from an input array $A$. It often leads to complexities like $O(n^2)$ (e.g., Insertion Sort).
  • Divide-and-Conquer: Breaks the problem into smaller, identical subproblems, solves them recursively, and combines the results.
  • This recursive strategy is powerful, leading to highly efficient algorithms like Merge Sort and Quick Sort.
  • Binary Search is a prime example, achieving $O(\log_2(n))$ time by repeatedly using the Divide step to eliminate half of the input array $A$.

Divide-and-Conquer: The 3 Steps

This powerful strategy breaks the original problem of size $n$ into several smaller, identical subproblems following a clear, recursive pattern:

Step Description
Divide Break the problem into smaller, self-similar subproblems.
Conquer Recursively solve the subproblems. If small enough, solve directly.
Combine Merge the subproblem solutions to get the final result.
Divide-and-Conquer Example (Python)
1# Divide-and-Conquer Example: Binary Search
2# Exploits the log2(n) complexity by dividing the search space.
3
4def binary_search_recursive(A, t, low, high):
5    # Base Case (Conquer: Problem size is 0 or t found)
6    if high < low:
7        return -1 # Target t not present
8    
9    # Divide step: Find pivot index (mid)
10    # We use Active_Pivot_Color (#3b82f6) for A[mid]
11    mid = (low + high) // 2
12    
13    # Comparison step (Comparison_Color: #f59e0b)
14    if A[mid] == t:
15        return mid 
16    elif A[mid] > t:
17        # Recursively search the left half
18        return binary_search_recursive(A, t, low, mid - 1)
19    else:
20        # Recursively search the right half
21        return binary_search_recursive(A, t, mid + 1, high)
22
23A_sorted = [4, 8, 15, 16, 23, 42] # Search_Array_A
24t_target = 23                     # Target_Value_t
25# Result should be index 4
26# print(binary_search_recursive(A_sorted, t_target, 0, len(A_sorted)-1))